package interviewpreparationkit.stringmanipulation

import java.util.*

/**
 * [Sherlock and the Valid String](https://www.hackerrank.com/challenges/sherlock-and-valid-string)
 */
fun isValid(s: String): String {
    val counts = s.groupBy { it }.map { it.value.size }.groupBy { it }
    if (counts.size == 1) return "YES"
    if (counts.size == 2) {
        val first = counts.values.first()
        val last = counts.values.last()
        if (last.size == 1) {
            if (last.first() - 1 == first.first() || last.first() == 1) {
                return "YES"
            }
        } else if (first.size == 1) {
            if (last.first() + 1 == first.first() || first.first() == 1) {
                return "YES"
            }
        }
    }
    return "NO"
}

/**
 * [Special Palindrome Again](https://www.hackerrank.com/challenges/special-palindrome-again)
 */
fun substrCount(n: Int, s: String): Long {
    val list = mutableListOf<Pair<Char, Int>>()
    var pre: Char = s[0]
    var start = 0

    s.forEachIndexed { index, c ->
        if (c != pre) {
            list.add(pre to index - start)
            start = index
        }
        pre = c
    }
    list.add(pre to n - start)

    var ans = 0L
    list.forEach {
        val m = it.second
        ans += (1 + m) * m / 2
    }

    for (i in 0 until list.size - 2) {
        if (list[i + 1].second == 1 && list[i].first == list[i + 2].first) {
            ans += kotlin.math.min(list[i].second, list[i + 2].second)
        }
    }

    return ans
}

/**
 * [Common Child](https://www.hackerrank.com/challenges/common-child)
 */
fun commonChild(s1: String, s2: String): Int {

    val bucket1 = Array(26) { 0 }
    val bucket2 = Array(26) { 0 }

    s1.forEach { bucket1[it - 'A']++ }
    s2.forEach { bucket2[it - 'A']++ }
    val bucket = Array(26) { kotlin.math.min(bucket1[it], bucket2[it]) }
    val str1 = s1.filter { bucket[it - 'A'] > 0 }
    val str2 = s2.filter { bucket[it - 'A'] > 0 }

    val c = Array(str1.length + 1) { Array(str2.length + 1) { _ -> 0 } }

    for (i in 1..str1.length)
        for (j in 1..str2.length) {
            when {
                str1[i - 1] == str2[j - 1] -> c[i][j] = c[i - 1][j - 1] + 1
                c[i][j - 1] > c[i - 1][j] -> c[i][j] = c[i][j - 1]
                else -> c[i][j] = c[i - 1][j]
            }
        }
    return c[str1.length][str2.length]
}